import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author：徐志荣
 * @Date：2023/9/7 上午 10:00
 */
public class Day0907 {
    public static void main(String[] args) {
       String s = "cbaebabacd";
       String p = "abc";
       System.out.println("438. 找到字符串中所有字母异位词:"+findAnagrams(s,p));
        String s1 = "barfoothefoobarman";
        String[] s2 = {"foo","bar"};
       System.out.println("30. 串联所有单词的子串 "+findSubstring(s1,s2));
    }
    public static List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //统计字符串p中每一个字符出现的个数
        int[] hash1 = new int[26];
        for(char ch : p){
            hash1[ch-'a']++;
        }

        //统计窗口中每一个字符出现的个数
        int[] hash2 = new int[26];
        int m = p.length;
        for(int left = 0,right = 0,count = 0;right<ss.length();right++){
            //进窗口
            char in = s[right];//获取 right处的值
            hash2[in-'a']++;  //记录该值++
            if(hash2[in-'a'] <= hash1[in-'a']){ //判断 hash2的值次数 是否是有效的
                count++;
            }
            //出窗口
            if(right-left+1 >m){  //窗口大小 大于  p的长度  ;说明需要出窗口
                char out = s[left];
                if(hash2[out -'a'] <= hash1[out -'a']){  //出窗口的值是有效的
                    count--;
                }
                hash2[out-'a']--;
                left++;
            }
            //更新结果
            if(count==m){
                ret.add(left);
            }

        }
        return ret;

    }


    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        //保存 words 中所有单词的频次
        Map<String,Integer> hash1 = new HashMap<String,Integer>();
        for(String str:words){
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }
        int len = words[0].length(); //滑动窗口执行的次数
        int m = words.length; // words 中的个数
        for(int i = 0;i<len;i++){
            Map<String,Integer> hash2 = new HashMap<String,Integer>();
            for(int left = i,right = i,count = 0;right+len<=s.length();right+=len){
                //进窗口
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)){  //hash2中的字符串 与 hash1中比较 ，看看是不是有效的？
                    count++;
                }
                //判断
                if(right-left+1>len*m){  //窗口大小是否正常？
                    //出窗口
                    String out = s.substring(left,left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.get(out)-1);
                    left+=len; //跨越一个字符串的长度
                }

                //更新结果
                if(count == m){
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}
